<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/blog/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/blog/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/blog/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/blog/images/logo.svg" color="#222">

<link rel="stylesheet" href="/blog/css/main.css">



<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.15.2/css/all.min.css">
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"littlefxc.github.io","root":"/blog/","images":"/blog/images","scheme":"Mist","version":"8.2.2","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":false,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/blog/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}};
  </script>
<meta name="description" content="概述双链表实现了List和Deque接口。 实现所有可选列表操作，并允许所有元素（包括null ）。 所有的操作都能像双向列表一样预期。 索引到列表中的操作将从开始或结束遍历列表，以更接近指定的索引为准。 请注意，此实现不同步。 如果多个线程同时访问链接列表，并且至少有一个线程在结构上修改列表，则必须在外部进行同步。 （结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。）这">
<meta property="og:type" content="article">
<meta property="og:title" content="Java集合学习之LinkedList">
<meta property="og:url" content="http://littlefxc.github.io/2019/05/23/Java%E9%9B%86%E5%90%88%E5%AD%A6%E4%B9%A0%E4%B9%8BLinkedList/index.html">
<meta property="og:site_name" content="一年春又来">
<meta property="og:description" content="概述双链表实现了List和Deque接口。 实现所有可选列表操作，并允许所有元素（包括null ）。 所有的操作都能像双向列表一样预期。 索引到列表中的操作将从开始或结束遍历列表，以更接近指定的索引为准。 请注意，此实现不同步。 如果多个线程同时访问链接列表，并且至少有一个线程在结构上修改列表，则必须在外部进行同步。 （结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。）这">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://littlefxc.github.io/2019/05/23/images/LinkedListUML.png">
<meta property="article:published_time" content="2019-05-23T01:51:14.000Z">
<meta property="article:modified_time" content="2021-03-25T13:15:48.964Z">
<meta property="article:author" content="一年春又来">
<meta property="article:tag" content="Java集合">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://littlefxc.github.io/2019/05/23/images/LinkedListUML.png">


<link rel="canonical" href="http://littlefxc.github.io/2019/05/23/Java%E9%9B%86%E5%90%88%E5%AD%A6%E4%B9%A0%E4%B9%8BLinkedList/">


<script class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>
<title>Java集合学习之LinkedList | 一年春又来</title>
  




  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

<link rel="alternate" href="/blog/atom.xml" title="一年春又来" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/blog/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">一年春又来</h1>
      <i class="logo-line"></i>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home"><a href="/blog/" rel="section"><i class="home                          //首页 fa-fw"></i>首页</a></li>
        <li class="menu-item menu-item-archives"><a href="/blog/archives/" rel="section"><i class="archive          //归档 fa-fw"></i>归档</a></li>
        <li class="menu-item menu-item-categories"><a href="/blog/categories/" rel="section"><i class="th           //分类 fa-fw"></i>分类</a></li>
        <li class="menu-item menu-item-tags"><a href="/blog/tags/" rel="section"><i class="tags                     //标签 fa-fw"></i>标签</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A6%82%E8%BF%B0"><span class="nav-text">概述</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%88%86%E6%9E%90"><span class="nav-text">分析</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AE%9A%E4%B9%89"><span class="nav-text">定义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%B1%9E%E6%80%A7"><span class="nav-text">属性</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%9E%84%E9%80%A0%E6%96%B9%E6%B3%95"><span class="nav-text">构造方法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A2%9E%E5%8A%A0-add-E-e"><span class="nav-text">增加 add(E e)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%A7%BB%E9%99%A4"><span class="nav-text">移除</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%9F%A5%E8%AF%A2"><span class="nav-text">查询</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%AD%E4%BB%A3%E5%99%A8-listIterator"><span class="nav-text">迭代器 listIterator</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%9C%89%E5%85%B3%E9%98%9F%E5%88%97%E3%80%81%E6%A0%88%E7%9A%84%E6%96%B9%E6%B3%95"><span class="nav-text">有关队列、栈的方法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#LinkedList-%E7%9A%84%E9%81%8D%E5%8E%86%E6%96%B9%E6%B3%95%E5%92%8C%E6%80%A7%E8%83%BD%E6%AF%94%E8%BE%83"><span class="nav-text">LinkedList 的遍历方法和性能比较</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BD%BF%E7%94%A8%E7%A4%BA%E4%BE%8B"><span class="nav-text">使用示例</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%80%BB%E7%BB%93"><span class="nav-text">总结</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">一年春又来</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/blog/archives/">
        
          <span class="site-state-item-count">184</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/blog/categories/">
          
        <span class="site-state-item-count">35</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/blog/tags/">
          
        <span class="site-state-item-count">115</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>



        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://littlefxc.github.io/2019/05/23/Java%E9%9B%86%E5%90%88%E5%AD%A6%E4%B9%A0%E4%B9%8BLinkedList/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/blog/images/avatar.gif">
      <meta itemprop="name" content="一年春又来">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="一年春又来">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          Java集合学习之LinkedList
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-05-23 09:51:14" itemprop="dateCreated datePublished" datetime="2019-05-23T09:51:14+08:00">2019-05-23</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-03-25 21:15:48" itemprop="dateModified" datetime="2021-03-25T21:15:48+08:00">2021-03-25</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/blog/categories/Java/" itemprop="url" rel="index"><span itemprop="name">Java</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><p>双链表实现了List和Deque接口。 实现所有可选列表操作，并允许所有元素（包括null ）。</p>
<p>所有的操作都能像双向列表一样预期。 索引到列表中的操作将从开始或结束遍历列表，以更接近指定的索引为准。</p>
<p><strong>请注意，此实现不同步。</strong> 如果多个线程同时访问链接列表，并且至少有一个线程在结构上修改列表，则必须在外部进行同步。 （结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。）<br>这通常通过在自然封装列表的对象上进行同步来实现。 如果没有这样的对象存在，列表应该使用 Collections.synchronizedList 方法“包装”。 这最好在创建时完成，以防止意外的不同步访问列表：</p>
<pre><code>List list = Collections.synchronizedList(new LinkedList(...)); 
</code></pre>
<p>这个类的 iterator 和 listIterator 方法返回的迭代器是故障快速的 ：如果列表在迭代器创建之后的任何时间被结构化地修改，除了通过迭代器自己的remove或add方法之外，<br>迭代器将会抛出一个ConcurrentModificationException 。 因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。</p>
<p>请注意，迭代器的故障快速行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。<br>失败快速迭代器尽力投入ConcurrentModificationException 。 因此，编写依赖于此异常的程序的正确性将是错误的：迭代器的故障快速行为应仅用于检测错误。</p>
<p>（以上来自 Java8 api）</p>
<h2 id="分析"><a href="#分析" class="headerlink" title="分析"></a>分析</h2><p>首先看一下 LinkedList 的继承关系：</p>
<p><img src="../images/LinkedListUML.png" alt="LinkedListUML.png"></p>
<h3 id="定义"><a href="#定义" class="headerlink" title="定义"></a>定义</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LinkedList</span>&lt;<span class="title">E</span>&gt;</span></span><br><span class="line"><span class="class">    <span class="keyword">extends</span> <span class="title">AbstractSequentialList</span>&lt;<span class="title">E</span>&gt;</span></span><br><span class="line"><span class="class">    <span class="keyword">implements</span> <span class="title">List</span>&lt;<span class="title">E</span>&gt;, <span class="title">Deque</span>&lt;<span class="title">E</span>&gt;, <span class="title">Cloneable</span>, <span class="title">java</span>.<span class="title">io</span>.<span class="title">Serializable</span></span>&#123;&#125;</span><br></pre></td></tr></table></figure>

<ol>
<li>LinkedList 是一个继承于 AbstractSequentialList 的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。<br>最大限度地减少了实现受“连续访问”数据存储（如链接列表）支持的此接口所需的工作,从而以减少实现 List 接口的复杂度。</li>
<li>LinkedList 实现 List 接口，能对它进行序列（有序集合）操作。</li>
<li>LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。</li>
<li>LinkedList 实现了 Cloneable 接口，即覆盖了函数 clone()，能克隆。</li>
<li>LinkedList 实现 java.io.Serializable 接口，这意味着 LinkedList 支持序列化，能通过序列化去传输。</li>
<li>LinkedList 是非同步的。</li>
</ol>
<h3 id="属性"><a href="#属性" class="headerlink" title="属性"></a>属性</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LinkedList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">extends</span> <span class="title">AbstractSequentialList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">implements</span> <span class="title">List</span>&lt;<span class="title">E</span>&gt;, <span class="title">Deque</span>&lt;<span class="title">E</span>&gt;, <span class="title">Cloneable</span>, <span class="title">java</span>.<span class="title">io</span>.<span class="title">Serializable</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> size = <span class="number">0</span>;<span class="comment">// list中的元素个数</span></span><br><span class="line">    </span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 链表头节点</span></span><br><span class="line"><span class="comment">     * 不变式: (first == null &amp;&amp; last == null) || (first.prev == null &amp;&amp; first.item != null)</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> Node&lt;E&gt; first;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 链表尾节点</span></span><br><span class="line"><span class="comment">     * 不变式: (first == null &amp;&amp; last == null) || (last.next == null &amp;&amp; last.item != null)</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> Node&lt;E&gt; last;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">E</span>&gt; </span>&#123;</span><br><span class="line">        E item;<span class="comment">// 实际存放的元素</span></span><br><span class="line">        Node&lt;E&gt; next;<span class="comment">// 后一个节点</span></span><br><span class="line">        Node&lt;E&gt; prev;<span class="comment">// 前一个节点</span></span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 构造函数元素顺序分别为前，自己，后。就像排队一样</span></span><br><span class="line">        Node(Node&lt;E&gt; prev, E element, Node&lt;E&gt; next) &#123;</span><br><span class="line">            <span class="keyword">this</span>.item = element;</span><br><span class="line">            <span class="keyword">this</span>.next = next;</span><br><span class="line">            <span class="keyword">this</span>.prev = prev;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;        </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="构造方法"><a href="#构造方法" class="headerlink" title="构造方法"></a>构造方法</h3><p>由于采用的是链表结构，所以不像 ArrayList 一样，有指定容量的构造方法</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LinkedList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">extends</span> <span class="title">AbstractSequentialList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">implements</span> <span class="title">List</span>&lt;<span class="title">E</span>&gt;, <span class="title">Deque</span>&lt;<span class="title">E</span>&gt;, <span class="title">Cloneable</span>, <span class="title">java</span>.<span class="title">io</span>.<span class="title">Serializable</span></span>&#123;</span><br><span class="line">     </span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">      * 构造一个空列表.</span></span><br><span class="line"><span class="comment">      */</span></span><br><span class="line">     <span class="function"><span class="keyword">public</span> <span class="title">LinkedList</span><span class="params">()</span> </span>&#123;</span><br><span class="line">     &#125;</span><br><span class="line">    </span><br><span class="line">     <span class="comment">/**</span></span><br><span class="line"><span class="comment">      * 构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列</span></span><br><span class="line"><span class="comment">      */</span></span><br><span class="line">     <span class="function"><span class="keyword">public</span> <span class="title">LinkedList</span><span class="params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;</span><br><span class="line">         <span class="keyword">this</span>();<span class="comment">// 什么都不做</span></span><br><span class="line">         addAll(c);<span class="comment">// 将 c 集合里的元素添加进链表</span></span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     <span class="comment">/**</span></span><br><span class="line"><span class="comment">       * 按照指定集合的迭代器返回的顺序将指定集合中的所有元素追加到此列表的末尾。</span></span><br><span class="line"><span class="comment">       */</span></span><br><span class="line">      <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">addAll</span><span class="params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;</span><br><span class="line">          <span class="keyword">return</span> addAll(size, c);</span><br><span class="line">      &#125;</span><br><span class="line">      </span><br><span class="line">      <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">checkPositionIndex</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">          <span class="keyword">if</span> (!isPositionIndex(index))</span><br><span class="line">              <span class="keyword">throw</span> <span class="keyword">new</span> IndexOutOfBoundsException(outOfBoundsMsg(index));</span><br><span class="line">      &#125;</span><br><span class="line">      </span><br><span class="line">      <span class="comment">/**</span></span><br><span class="line"><span class="comment">        * 判断参数是迭代器或添加操作的有效位置的索引。</span></span><br><span class="line"><span class="comment">        */</span></span><br><span class="line">       <span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">isPositionIndex</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">           <span class="keyword">return</span> index &gt;= <span class="number">0</span> &amp;&amp; index &lt;= size;</span><br><span class="line">       &#125;</span><br><span class="line">  </span><br><span class="line">      <span class="comment">/**</span></span><br><span class="line"><span class="comment">       * 从指定位置开始，将指定集合中的所有元素插入此列表。 </span></span><br><span class="line"><span class="comment">       * 将当前位置的元素（如果有）和任何后续元素向右移动（增加其索引）。 </span></span><br><span class="line"><span class="comment">       * 新元素将按照指定集合的迭代器返回的顺序出现在列表中。</span></span><br><span class="line"><span class="comment">       */</span></span><br><span class="line">      <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">addAll</span><span class="params">(<span class="keyword">int</span> index, Collection&lt;? extends E&gt; c)</span> </span>&#123;</span><br><span class="line">          checkPositionIndex(index);<span class="comment">// 检查索引是否正确，即在 0 &lt;= index &lt;= size</span></span><br><span class="line">  </span><br><span class="line">          Object[] a = c.toArray();<span class="comment">// 将 collection 转为数组</span></span><br><span class="line">          <span class="keyword">int</span> numNew = a.length;</span><br><span class="line">          <span class="keyword">if</span> (numNew == <span class="number">0</span>)</span><br><span class="line">              <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">  </span><br><span class="line">          Node&lt;E&gt; pred, succ;<span class="comment">// 声明 pred 为&quot;当前要插入节点的前一个节点&quot;，succ 为&quot;当前要插入节点的后一个节点&quot;</span></span><br><span class="line">          <span class="keyword">if</span> (index == size) &#123;<span class="comment">// 说明要插入元素的位置就在链表的末尾，后置元素为null，前一个元素就是last</span></span><br><span class="line">              succ = <span class="keyword">null</span>;</span><br><span class="line">              pred = last;</span><br><span class="line">          &#125; <span class="keyword">else</span> &#123; <span class="comment">// 说明在链表的中间插入，这时 pred 为原来 index 的 prev，succ 为原来的元素</span></span><br><span class="line">              succ = node(index);<span class="comment">// 利用双向链表的特性，进行更快的遍历</span></span><br><span class="line">              pred = succ.prev;</span><br><span class="line">          &#125;</span><br><span class="line">  </span><br><span class="line">          <span class="keyword">for</span> (Object o : a) &#123;<span class="comment">// 遍历数组，逐个添加</span></span><br><span class="line">              <span class="meta">@SuppressWarnings(&quot;unchecked&quot;)</span> E e = (E) o;</span><br><span class="line">              Node&lt;E&gt; newNode = <span class="keyword">new</span> Node&lt;&gt;(pred, e, <span class="keyword">null</span>);</span><br><span class="line">              <span class="keyword">if</span> (pred == <span class="keyword">null</span>)</span><br><span class="line">                  first = newNode;</span><br><span class="line">              <span class="keyword">else</span></span><br><span class="line">                  pred.next = newNode;</span><br><span class="line">              pred = newNode;<span class="comment">// 将新节点作为pred，为下一个元素插入做准备</span></span><br><span class="line"></span><br><span class="line">          &#125;</span><br><span class="line">  </span><br><span class="line">          <span class="keyword">if</span> (succ == <span class="keyword">null</span>) &#123;<span class="comment">// 如果后继元素为空，那么插入完后的最后一个元素，就 pred 就是 last</span></span><br><span class="line">              last = pred;</span><br><span class="line">          &#125; <span class="keyword">else</span> &#123;<span class="comment">// 否则就维护最后一个元素和之前的元素之间的关系</span></span><br><span class="line">              pred.next = succ;</span><br><span class="line">              succ.prev = pred;</span><br><span class="line">          &#125;</span><br><span class="line">  </span><br><span class="line">          size += numNew;</span><br><span class="line">          modCount++;<span class="comment">// 链表结构发生改动</span></span><br><span class="line">          <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">      &#125;</span><br><span class="line">      </span><br><span class="line">      <span class="comment">/**</span></span><br><span class="line"><span class="comment">       * 返回指定元素索引处的(非空)节点</span></span><br><span class="line"><span class="comment">       * 利用双向链表的特性，进行更快的遍历</span></span><br><span class="line"><span class="comment">       * 双向链表和索引值联系起来：通过一个计数索引值来实现</span></span><br><span class="line"><span class="comment">       *    当我们调用get(int index)时，首先会比较“index”和“双向链表长度的1/2”；</span></span><br><span class="line"><span class="comment">       *    若前者大，则从链表头开始往后查找，直到 index 位置；</span></span><br><span class="line"><span class="comment">       *    否则，从链表末尾开始先前查找，直到 index 位置.</span></span><br><span class="line"><span class="comment">       */</span></span><br><span class="line">      <span class="function">Node&lt;E&gt; <span class="title">node</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">          <span class="comment">// assert isElementIndex(index);</span></span><br><span class="line">      </span><br><span class="line">          <span class="keyword">if</span> (index &lt; (size &gt;&gt; <span class="number">1</span>)) &#123;<span class="comment">// 如果index在链表的前半部分，则从头部节点开始遍历</span></span><br><span class="line">              Node&lt;E&gt; x = first;</span><br><span class="line">              <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; index; i++)</span><br><span class="line">                  x = x.next;</span><br><span class="line">              <span class="keyword">return</span> x;</span><br><span class="line">          &#125; <span class="keyword">else</span> &#123;<span class="comment">// 如果index在链表的后半部分，则从尾部节点开始遍历</span></span><br><span class="line">              Node&lt;E&gt; x = last;</span><br><span class="line">              <span class="keyword">for</span> (<span class="keyword">int</span> i = size - <span class="number">1</span>; i &gt; index; i--)</span><br><span class="line">                  x = x.prev;</span><br><span class="line">              <span class="keyword">return</span> x;</span><br><span class="line">          &#125;</span><br><span class="line">      &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="增加-add-E-e"><a href="#增加-add-E-e" class="headerlink" title="增加 add(E e)"></a>增加 add(E e)</h3><p>作为链表，添加新元素就是在链表的末尾插入新元素。</p>
<p>注意，如果末尾元素是 null ，又该如何处理？</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LinkedList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">extends</span> <span class="title">AbstractSequentialList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">implements</span> <span class="title">List</span>&lt;<span class="title">E</span>&gt;, <span class="title">Deque</span>&lt;<span class="title">E</span>&gt;, <span class="title">Cloneable</span>, <span class="title">java</span>.<span class="title">io</span>.<span class="title">Serializable</span></span>&#123;</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 将指定的元素追加到此列表的末尾。</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">add</span><span class="params">(E e)</span> </span>&#123;</span><br><span class="line">         linkLast(e);</span><br><span class="line">         <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 链接 e 作为最后一个元素。</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">linkLast</span><span class="params">(E e)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">final</span> Node&lt;E&gt; l = last;<span class="comment">// 记录last节点</span></span><br><span class="line">        <span class="keyword">final</span> Node&lt;E&gt; newNode = <span class="keyword">new</span> Node&lt;&gt;(l, e, <span class="keyword">null</span>);<span class="comment">// 初始化新的节点</span></span><br><span class="line"></span><br><span class="line">        last = newNode;</span><br><span class="line">        <span class="keyword">if</span> (l == <span class="keyword">null</span>)<span class="comment">// 末尾元素是 null,是个空列表</span></span><br><span class="line">            first = newNode;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            l.next = newNode;</span><br><span class="line">        size++;</span><br><span class="line">        modCount++;<span class="comment">// 链表结构发生改动</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>LinkedList 还有其他的增加方法：</p>
<ul>
<li>add(int index, E element)：在此列表中指定的位置插入指定的元素。</li>
<li>addAll(Collection&lt;? extends E&gt; c)：添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。</li>
<li>addAll(int index, Collection&lt;? extends E&gt; c)：将指定 collection 中的所有元素从指定位置开始插入此列表。</li>
<li>AddFirst(E e): 将指定元素插入此列表的开头。</li>
<li>addLast(E e): 将指定元素添加到此列表的结尾。</li>
</ul>
<h3 id="移除"><a href="#移除" class="headerlink" title="移除"></a>移除</h3><p>处理思路：</p>
<ol>
<li>由于插入的元素可能为null，所以要对o进行判断，否则不论是o为null还是遍历的时候元素为null，都会导致报空指针异常</li>
<li>找到元素后，对前后的元素关系重新维护，要考虑到元素是否在头尾的情况</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LinkedList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">extends</span> <span class="title">AbstractSequentialList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">implements</span> <span class="title">List</span>&lt;<span class="title">E</span>&gt;, <span class="title">Deque</span>&lt;<span class="title">E</span>&gt;, <span class="title">Cloneable</span>, <span class="title">java</span>.<span class="title">io</span>.<span class="title">Serializable</span></span>&#123;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">remove</span><span class="params">(Object o)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (o == <span class="keyword">null</span>) &#123;<span class="comment">// 是否为 null 的判断</span></span><br><span class="line">            <span class="comment">// 从头节点遍历链表寻找第一个 x(null) 元素</span></span><br><span class="line">            <span class="keyword">for</span> (Node&lt;E&gt; x = first; x != <span class="keyword">null</span>; x = x.next) &#123;</span><br><span class="line">                <span class="keyword">if</span> (x.item == <span class="keyword">null</span>) &#123;</span><br><span class="line">                    unlink(x);<span class="comment">// 取消链接 x(null) 元素，重新维护删除元素后的前后关系</span></span><br><span class="line">                    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;<span class="comment">// 与上面的逻辑相同</span></span><br><span class="line">            <span class="keyword">for</span> (Node&lt;E&gt; x = first; x != <span class="keyword">null</span>; x = x.next) &#123;</span><br><span class="line">                <span class="keyword">if</span> (o.equals(x.item)) &#123;</span><br><span class="line">                    unlink(x);</span><br><span class="line">                    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Unlinks non-null node x.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function">E <span class="title">unlink</span><span class="params">(Node&lt;E&gt; x)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// assert x != null;</span></span><br><span class="line">        <span class="keyword">final</span> E element = x.item;</span><br><span class="line">        <span class="comment">// 局部保存被删除节点的前后节点</span></span><br><span class="line">        <span class="keyword">final</span> Node&lt;E&gt; next = x.next;</span><br><span class="line">        <span class="keyword">final</span> Node&lt;E&gt; prev = x.prev;</span><br><span class="line">    </span><br><span class="line">        <span class="keyword">if</span> (prev == <span class="keyword">null</span>) &#123;<span class="comment">// prev 为 null 说明 x 节点为 first 节点，则删除后，next 为 first</span></span><br><span class="line">            first = next;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;<span class="comment">// 否则 prev的下一个元素为x的next</span></span><br><span class="line">            prev.next = next;</span><br><span class="line">            x.prev = <span class="keyword">null</span>;<span class="comment">// 设为 null，方便GC</span></span><br><span class="line">        &#125;</span><br><span class="line">    </span><br><span class="line">        <span class="keyword">if</span> (next == <span class="keyword">null</span>) &#123;<span class="comment">// next 为null说明x节点为 last 节点，则删除后，next 为 prev</span></span><br><span class="line">            last = prev;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;<span class="comment">// 否则 next 的上一个元素为x的prev</span></span><br><span class="line">            next.prev = prev;</span><br><span class="line">            x.next = <span class="keyword">null</span>;<span class="comment">// 设为 null，方便GC</span></span><br><span class="line">        &#125;</span><br><span class="line">    </span><br><span class="line">        x.item = <span class="keyword">null</span>;<span class="comment">// 设为 null，方便GC</span></span><br><span class="line">        size--;</span><br><span class="line">        modCount++;<span class="comment">// 链表结构发生改变</span></span><br><span class="line">        <span class="keyword">return</span> element;<span class="comment">//返回被删除节点的数据体</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>其他的移除方法：</p>
<ul>
<li>clear()： 从此列表中移除所有元素。</li>
<li>remove()：获取并移除此列表的头（第一个元素）。</li>
<li>remove(int index)：移除此列表中指定位置处的元素。</li>
<li>remove(Objec o)：从此列表中移除首次出现的指定元素（如果存在）。</li>
<li>removeFirst()：移除并返回此列表的第一个元素。</li>
<li>removeFirstOccurrence(Object o)：从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。</li>
<li>removeLast()：移除并返回此列表的最后一个元素。</li>
<li>removeLastOccurrence(Object o)：从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。</li>
</ul>
<h3 id="查询"><a href="#查询" class="headerlink" title="查询"></a>查询</h3><p>查询的方法非常简单，</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LinkedList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">extends</span> <span class="title">AbstractSequentialList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">implements</span> <span class="title">List</span>&lt;<span class="title">E</span>&gt;, <span class="title">Deque</span>&lt;<span class="title">E</span>&gt;, <span class="title">Cloneable</span>, <span class="title">java</span>.<span class="title">io</span>.<span class="title">Serializable</span></span>&#123;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> E <span class="title">get</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">        checkElementIndex(index);<span class="comment">// 检查索引index 是否在 [0,size] 区间内</span></span><br><span class="line">        <span class="keyword">return</span> node(index).item;<span class="comment">//利用双向链表的特性，进行更快的遍历</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>其它的查询方法：</p>
<ul>
<li>getFirst()：返回此列表的第一个元素。</li>
<li>getLast()：返回此列表的最后一个元素。</li>
<li>indexOf(Object o)：返回此列表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。</li>
<li>lastIndexOf(Object o)：返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。</li>
</ul>
<h3 id="迭代器-listIterator"><a href="#迭代器-listIterator" class="headerlink" title="迭代器 listIterator"></a>迭代器 listIterator</h3><p>关于集合的快速失败机制的详细了解可以<a href="Java%E9%9B%86%E5%90%88%E5%AD%A6%E4%B9%A0%E4%B9%8Bfail-fast.md">看这里</a></p>
<p>iterator() 调用的其实是 listIterator() 方法，对于不同的实现类，都会实现不同的方法，但是其原理是一致的，<br>都是为了防止多线程操作同一个集合而出现的问题</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LinkedList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">extends</span> <span class="title">AbstractSequentialList</span>&lt;<span class="title">E</span>&gt; <span class="keyword">implements</span> <span class="title">List</span>&lt;<span class="title">E</span>&gt;, <span class="title">Deque</span>&lt;<span class="title">E</span>&gt;, <span class="title">Cloneable</span>, <span class="title">java</span>.<span class="title">io</span>.<span class="title">Serializable</span></span>&#123;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> ListIterator&lt;E&gt; <span class="title">listIterator</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">        checkPositionIndex(index);<span class="comment">// 检查索引的正确性[0, size]</span></span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> ListItr(index);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">ListItr</span> <span class="keyword">implements</span> <span class="title">ListIterator</span>&lt;<span class="title">E</span>&gt; </span>&#123;</span><br><span class="line">        <span class="keyword">private</span> Node&lt;E&gt; lastReturned;<span class="comment">// 记录上次返回的元素</span></span><br><span class="line">        <span class="keyword">private</span> Node&lt;E&gt; next;<span class="comment">// 记录下一个元素</span></span><br><span class="line">        <span class="keyword">private</span> <span class="keyword">int</span> nextIndex;</span><br><span class="line">        <span class="keyword">private</span> <span class="keyword">int</span> expectedModCount = modCount;<span class="comment">// 用来判断迭代过程中，是否有对元素的改动(fail-fast)</span></span><br><span class="line">    </span><br><span class="line">        ListItr(<span class="keyword">int</span> index) &#123;</span><br><span class="line">            <span class="comment">// assert isPositionIndex(index);</span></span><br><span class="line">            next = (index == size) ? <span class="keyword">null</span> : node(index);<span class="comment">//初始化next，以便在next方法中返回</span></span><br><span class="line">            nextIndex = index;</span><br><span class="line">        &#125;</span><br><span class="line">    </span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasNext</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> nextIndex &lt; size;</span><br><span class="line">        &#125;</span><br><span class="line">    </span><br><span class="line">        <span class="function"><span class="keyword">public</span> E <span class="title">next</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            checkForComodification();<span class="comment">// 判断是否有对元素的改动，有则抛出异常</span></span><br><span class="line">            <span class="keyword">if</span> (!hasNext())</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException();</span><br><span class="line">    </span><br><span class="line">            lastReturned = next;<span class="comment">// next()当中的next元素就是要返回的结果</span></span><br><span class="line">            next = next.next;</span><br><span class="line">            nextIndex++;</span><br><span class="line">            <span class="keyword">return</span> lastReturned.item;</span><br><span class="line">        &#125;</span><br><span class="line">    </span><br><span class="line">        <span class="comment">// 省略其它代码。。。</span></span><br><span class="line">    </span><br><span class="line">        <span class="function"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title">checkForComodification</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">if</span> (modCount != expectedModCount)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="有关队列、栈的方法"><a href="#有关队列、栈的方法" class="headerlink" title="有关队列、栈的方法"></a>有关队列、栈的方法</h3><ul>
<li>peek():返回第一个节点,若LinkedList的大小为0,则返回null</li>
<li>peekFirst():返回第一个节点,若LinkedList的大小为0,则返回null</li>
<li>peekLast():返回最后一个节点,若LinkedList的大小为0,则返回null</li>
<li>element():返回第一个节点,若LinkedList的大小为0,则抛出异常</li>
<li>poll():删除并返回第一个节点,若LinkedList的大小为0,则返回null</li>
<li>pollFirst():删除并返回第一个节点,若LinkedList的大小为0,则返回null</li>
<li>pollLast():删除并返回最后一个节点,若LinkedList的大小为0,则返回null</li>
<li>offer(E e):将e添加双向链表末尾</li>
<li>offerFirst(E e):将e添加双向链表开头</li>
<li>offerLast(E e):将e添加双向链表末尾</li>
<li>push(E e):将e插入到双向链表开头</li>
<li>pop():删除并返回第一个节点</li>
</ul>
<p>LinkedList 作为 FIFO(先进先出) 的队列, 下表的方法等效：</p>
<table>
<thead>
<tr>
<th>队列方法</th>
<th>等效方法</th>
</tr>
</thead>
<tbody><tr>
<td>add(e)</td>
<td>addLast(e)</td>
</tr>
<tr>
<td>offer(e)</td>
<td>offerLast(e)</td>
</tr>
<tr>
<td>remove()</td>
<td>removeFirst()</td>
</tr>
<tr>
<td>poll()</td>
<td>pollFirst()</td>
</tr>
<tr>
<td>element()</td>
<td>getFirst()</td>
</tr>
<tr>
<td>peek()</td>
<td>peekFirst()</td>
</tr>
</tbody></table>
<p>LinkedList 作为 LIFO(后进先出) 的栈, 下表的方法等效：</p>
<table>
<thead>
<tr>
<th>栈方法</th>
<th>等效方法</th>
</tr>
</thead>
<tbody><tr>
<td>push(e)</td>
<td>addFirst(e)</td>
</tr>
<tr>
<td>pop()</td>
<td>removeFirst()</td>
</tr>
<tr>
<td>peek()</td>
<td>peekFirst()</td>
</tr>
</tbody></table>
<h3 id="LinkedList-的遍历方法和性能比较"><a href="#LinkedList-的遍历方法和性能比较" class="headerlink" title="LinkedList 的遍历方法和性能比较"></a>LinkedList 的遍历方法和性能比较</h3><h3 id="使用示例"><a href="#使用示例" class="headerlink" title="使用示例"></a>使用示例</h3><h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><ol>
<li>LinkedList 实际上是通过双向链表去实现的。它包含一个非常重要的内部类：<code>Node</code>。<code>Node</code> 是双向链表节点所对应的数据结构，<br>它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。</li>
<li>从 LinkedList 的实现方式中可以发现，它不存在LinkedList容量不足的问题。</li>
<li>LinkedList 的克隆函数，即是将全部元素克隆到一个新的LinkedList对象中。</li>
<li>LinkedList 实现java.io.Serializable。当写入到输出流时，先写入“容量”，再依次写入“每一个节点保护的值”；<br>当读出输入流时，先读取“容量”，再依次读取“每一个元素”。</li>
<li>由于 LinkedList 实现了Deque，而 Deque 接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。<br>每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。</li>
</ol>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/blog/tags/Java%E9%9B%86%E5%90%88/" rel="tag"># Java集合</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/blog/2019/05/14/Java%E9%9B%86%E5%90%88%E5%AD%A6%E4%B9%A0%E4%B9%8Bfail-fast/" rel="prev" title="Java集合学习之fail-fast">
                  <i class="fa fa-chevron-left"></i> Java集合学习之fail-fast
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/blog/2019/05/23/Consul%E4%BD%BF%E7%94%A8%E8%AE%B0%E5%BD%95/" rel="next" title="Consul使用记录">
                  Consul使用记录 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>







<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">一年春又来</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/mist/" class="theme-link" rel="noopener" target="_blank">NexT.Mist</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <script src="https://cdn.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js"></script>
<script src="/blog/js/utils.js"></script><script src="/blog/js/motion.js"></script><script src="/blog/js/schemes/muse.js"></script><script src="/blog/js/next-boot.js"></script>

  
<script src="/blog/js/local-search.js"></script>






  





</body>
</html>
